"MATRIX_CHAIN_ORDER Chapter 15"

def MATRIX_CHAIN_ORDER(p):
    n=len(p)-1
    'init m'
    m=[[0 for col in range(n)] for row in range(n)]
    s=[[0 for col in range(n)] for row in range(n)]
    HUGE=10000000000000
    
    for l in range(1,n):
        for i in range(n-l+1):
            j=i+l-1
            m[i][j]=HUGE
            for k in range(i,j-1):
                q=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]
                if q<m[i][j]:
                    m[i][j]=q
                    s[i][j]=k
    print(m)     
    print("_____________")
    print(s)
                
    pass

if __name__=='__main__':
    arr=(30,35,15,5,10,20,25)
    MATRIX_CHAIN_ORDER(arr)
    print('MATRIX_CHAIN_ORDER')
